package tum0r.data.structure;

import java.util.HashSet;

/**
 * 工程: JavaTools<br>
 * 包: tum0r.data.structure<br>
 * 创建者: tum0r<br>
 * 创建时间: 2020/8/21 23:23<br>
 * <br>
 */
public class UnionFindSet {
    private int[][] array;
    private int length = -1;

    public void init(int n) {
        array = new int[2][n];
        length = n;
        for (int i = 0; i < length; i++) {
            array[0][i] = i;
            array[1][i] = i;
        }
    }

    public boolean setContact(int from, int to) {
        if (array != null && from >= 1 && from <= length && to >= 1 && to <= length) {
            array[1][--from] = (--to);
            compression();
            return true;
        }
        return false;
    }

    public int getResult() {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < length; i++) {
            set.add(array[1][i]);
        }
        return set.size();
    }

    private void compression() {
        int index = 0;
        for (int i = 0; i < array.length; i++) {
            index = getFinal(i);
            if (array[1][i] != index) {
                array[1][i] = index;
            }
        }
    }

    private int getFinal(int index) {
        if (array[0][index] == array[1][index]) {
            return index;
        }
        return getFinal(array[1][index]);
    }
}
